package com.leetcode.LC;

public class LC69 {
    public int mySqrt(int x) {

        int a = 0, b = x, mid = 0;
        long s = 0;
        while (a <= b) {
            mid = a + (b - a) / 2;
            s = (long) mid * mid;
            if (s == x) {
                return mid;
            } else if (s < x) {
                a = mid + 1;
            } else if (s > x) {
                b = mid - 1;
            }
        }
        return (s) < x ? mid : mid - 1;

    }

    public int mySqrt2(int x) {
        int l = 0, r = x, ans = -1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if ((long) mid * mid <= x) {
                ans = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return ans;
    }


    public static void main(String[] args) {
        System.out.println(new LC69().mySqrt(2147395599));
    }
}
